package Datas_Structure.Tree;

/**
 * 创建二叉树
 * 满二叉树：
 * 所有的叶子节点都在最后一层，而且节点的总数为：2^n-1,n是树的高度
 * 完全二叉树：
 * 所有的叶子节点都在最后一层或倒数第二层，且最后一层的叶子节点再左边连续，倒数第二层的叶子节点在右边连续
 */
public class binaryTree {
    //根节点
    TreeNode root;

    //get/set
    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    //1.前序遍历
    public void frontSearch() {
        root.frontSearch();

    }

    //2.中序遍历
    public void midSearch() {
        root.midSearch();
    }

    //3.后序遍历
    public void lastSearch() {
        root.lastSearch();
    }

    //查找一个值
    public TreeNode frontFind(int i) {
        return root.frontFind(i);
    }
//删除一个节点
    public void delet(int i) {
        if (root.value == i){
            root = null;
        }else {
            root.delet(i);
        }
    }
}

/**
 * 创建节点
 */
class TreeNode {
    //权值
    int value;
    //左儿子
    TreeNode lNode;
    //右儿子
    TreeNode rNode;

    //有参构造器
    public TreeNode(int value) {
        this.value = value;
    }

    //set
    public void setlNode(TreeNode lNode) {
        this.lNode = lNode;
    }

    public void setrNode(TreeNode rNode) {
        this.rNode = rNode;
    }
    //get

    public TreeNode getlNode() {
        return lNode;
    }

    public TreeNode getrNode() {
        return rNode;
    }

    //1.前序遍历
    public void frontSearch() {
        //打印当前节点
        System.out.print(value + " ");
        //左节点
        if (lNode != null) {
            lNode.frontSearch();
            //右节点
        }
        if (rNode != null) {
            rNode.frontSearch();
        }
    }

    //2.中序遍历
    public void midSearch() {
        if (lNode != null) {
            lNode.midSearch();
        }
        System.out.print(value + " ");
        if (rNode != null) {
            rNode.midSearch();
        }


    }

    //3.后序遍历
    public void lastSearch() {
        if (lNode != null) {
            lNode.midSearch();
        }
        if (rNode != null) {
            rNode.midSearch();
        }
        System.out.print(value + " ");
    }

    //查找一个值
    public TreeNode frontFind(int i) {
        //变量
        TreeNode target = null;
        //如果是当前节点，就返回
        if (this.value == i) {
            return this;
        } else {
            //如果不是则遍历左子树
            if (lNode != null) {
                target = lNode.frontFind(i);
            }
            //如果target不为空，则找到
            if (target != null) {
                return target;
            }
            //如过target为空，则则查找右子树
            if (rNode != null) {
                target = rNode.frontFind(i);
            }
        }
        return target;
    }

    //删除一个节点
    public void delet(int i) {
        TreeNode current = this;
        //删除左节点
        if (current.lNode!=null&&current.lNode.value == i) {
            current.lNode = null;
            return;
        }
        //删除右节点
        if (current.rNode!=null&&current.rNode.value == i) {
            current.rNode = null;
            return;
        }
        //查找并删除左节点
        current = lNode;
        if (current != null) {
            current.delet(i);
        }
        //查找并删除右节点
        current = rNode;
        if (current != null) {
            current.delet(i);
        }
    }
}

/**
 * 测试
 */
class binaryTreeTest {
    public static void main(String[] args) {
        //创建一个树
        binaryTree tree = new binaryTree();
        //创建一个节点
        TreeNode root = new TreeNode(1);
        tree.setRoot(root);
        //创建左儿子
        TreeNode lnode = new TreeNode(2);
        root.setlNode(lnode);
        //创建右儿子
        TreeNode rnode = new TreeNode(3);
        root.setrNode(rnode);

        //再给lnode创建二个儿子
        lnode.setlNode(new TreeNode(4));
        lnode.setrNode(new TreeNode(5));

        //再给rnode创建二个儿子
        rnode.setlNode(new TreeNode(6));
        rnode.setrNode(new TreeNode(7));
        /**
         * 前序遍历
         * 先根，再左，再右
         */
        System.out.println("前序遍历: ");
        tree.frontSearch();

        /**
         * 中序遍历
         * 先左，再根，再右
         */
        System.out.println();
        System.out.println("中序遍历: ");
        tree.midSearch();
        /**
         * 后序遍历
         * 先左，再右，在根
         */
        System.out.println();
        System.out.println("后序遍历: ");
        tree.lastSearch();
        /**
         *查找一个值
         */
        System.out.println();
        System.out.println("查找一个数: " + tree.frontFind(1).value);
        /**
         * 删除一个节点
         */
        System.out.println();
        System.out.println("删除一个数: ");
        tree.delet(2);
        tree.midSearch();
    }
}